/**
 * @ClassName KP31_CreateBinaryTreeFromPreorderAndInorderTraversal
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/26 12:56
 */

import java.util.HashMap;

/**
 * 从前序与中序遍历序列构造二叉树
 */
public class KP31_CreateBinaryTreeFromPreorderAndInorderTraversal {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        return createTree1(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode createTree1(int[] preorder, int preStartIndex, int preEndIndex, int[] inorder, int inStartIndex, int inEndIndex) {
        if (preStartIndex > preEndIndex) {
            return null;
        }
        TreeNode head = new TreeNode(preorder[preStartIndex]);
        if (preStartIndex == preEndIndex) {
            return head;
        }
        int find = inStartIndex;
        for (; find <= inEndIndex && inorder[find] != preorder[preStartIndex]; find++) ;
        head.left = createTree1(preorder, preStartIndex + 1, preStartIndex + find - inStartIndex, inorder, inStartIndex, find - 1);
        head.right = createTree1(preorder, preStartIndex + find - inStartIndex + 1, preEndIndex, inorder, find + 1, inEndIndex);
        return head;
    }

    // 优化
    // 时间复杂度 O(N)
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i], i);
        }
        return createTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, hashMap);
    }

    public TreeNode createTree(int[] preorder, int preStartIndex, int preEndIndex, int[] inorder, int inStartIndex, int inEndIndex, HashMap hashMap) {
        if (preStartIndex > preEndIndex) {
            return null;
        }
        TreeNode head = new TreeNode(preorder[preStartIndex]);
        if (preStartIndex == preEndIndex) {
            return head;
        }
        int find = (int) hashMap.get(preorder[preStartIndex]);
        head.left = createTree(preorder, preStartIndex + 1, preStartIndex + find - inStartIndex, inorder, inStartIndex, find - 1, hashMap);
        head.right = createTree(preorder, preStartIndex + find - inStartIndex + 1, preEndIndex, inorder, find + 1, inEndIndex, hashMap);
        return head;
    }
}
